Section: New Results

Effective heuristics for matchings in hypergraphs

The problem of finding a maximum cardinality matching in a $d$-partite, $d$-uniform hypergraph is an important problem in combinatorial optimization and has been theoretically analyzed. We first generalize some graph matching heuristics for this problem. We then propose a novel heuristic based on tensor scaling to extend the matching via judicious hyperedge selections. Experiments on random, synthetic and real-life hypergraphs show that this new heuristic is highly practical and superior to the others on finding a matching with large cardinality.

This work is published in the proceedings of SEA${}^2$, where it has received the best paper award [16].